package at.fhooe.mc.task02;

import at.fhooe.mc.task01.Sorter;
import at.fhooe.mc.task01and02.*;

/**
 * @author Felix Gruber <br>
 *         S1310237015 <br>
 *         Mobile Computing <br>
 *         FH Hagenberg
 */
public class Mergesort<T> implements Sorter<T> {
	private Comparable[] values, helper;

	public void sort(Comparable<T>[] a) {
		this.values = a;
		this.helper = new Comparable[values.length];
		msort(0, values.length - 1);
	}

	private void msort(int from, int to) {
		if (from < to) {
			int middle = from + (to - from) / 2;
			msort(from, middle);
			msort(middle + 1, to);
			merge(from, middle, to);
		}
	}

	private void merge(int from, int middle, int to) {
		for (int i = from; i <= to; i++) {
			helper[i] = values[i];
		}
		int i = from, j = middle + 1, k = from;
		while (i <= middle && j <= to) {
			if (helper[i].compareTo(helper[j]) <= 0) {
				values[k] = helper[i];
				i++;
			} else {
				values[k] = helper[j];
				j++;
			}
			k++;
		}
		while (i <= middle) {
			values[k] = helper[i];
			k++;
			i++;
		}
	}
}